ICPC Live Archive/3928 - Ballroom lights/help/gomox.ar-pap-2010-d9b17e5cb110/tpd/gnu/gnu.cpp

   1 #include <vector>
   2 #include <cstdio>
   3 #include <iostream>
   4 #include <cassert>
   5 #include <cstring>
   6
   7 using namespace std;
   8
   9 typedef unsigned long long int lluint;
  10
  11 typedef vector<lluint> Row;
  12 typedef vector<Row> Mat;
  13
  14 #define forsn(i, s, n)  for (int i = (s); i < (n); i++)
  15 #define forn(i, n)      forsn (i, 0, n)
  16
  17 void mat_mult(const Mat& m1, const Mat& m2, Mat& res) {
  18     const int n = m1.size();
  19     const int m = m2.size();
  20     const int p = m2[0].size();
  21     assert(m1[0].size() == m && res.size() == n && res[0].size() == p);
  22     forn (i, n) forn (j, p) {
  23         lluint s = 0;
  24         forn (k, m) s += m1[i][k] * m2[k][j];
  25         res[i][j] = s;
  26     }
  27 }
  28
  29 void mat_identity(Mat& mt) {
  30     const int n = mt.size();
  31     assert(n == mt[0].size());
  32     forn (i, n) forn (j, n) {
  33         mt[i][j] = i == j;
  34     }
  35 }
  36
  37 void mat_copy(const Mat& in, Mat& out) {
  38     const int n = in.size();
  39     const int m = in[0].size();
  40     assert(out.size() == in.size() && out[0].size() == in[0].size());
  41     forn (i, n) forn (j, m) out[i][j] = in[i][j];
  42 }
  43
  44 void mat_pow(const Mat& mt, int pow, Mat& res) {
  45     const int n = mt.size();
  46     vector<Mat> acc(2, Mat(n, Row(n, 0)));
  47     mat_identity(res);
  48     mat_copy(mt, acc[false]);
  49     bool cur = false;
  50     for (;;) {
  51         if (pow & 1) {
  52             mat_copy(res, acc[!cur]);
  53             mat_mult(acc[!cur], acc[cur], res);
  54         }
  55         pow >>= 1;
  56         if (pow == 0) break;
  57         mat_mult(acc[cur], acc[cur], acc[!cur]);
  58         cur = !cur;
  59     }
  60 }
  61
  62 void mat_print(const Mat& mt) {
  63     const int n = mt.size();
  64     const int m = mt[0].size();
  65     forn (i, n) {
  66         forn (j, m) {
  67             cout << mt[i][j] << " ";
  68         }
  69         cout << endl;
  70     }
  71 }
  72
  73 #define MIN_CHAR        32
  74 #define MAX_CHAR        127
  75 #define N               (MAX_CHAR - MIN_CHAR + 1)
  76
  77 #define in_range(Char)  (MIN_CHAR <= (Char) <= MAX_CHAR)
  78 #define charcode(Char)  ((Char) - MIN_CHAR)
  79
  80 #define Max_rule        1024
  81 int main() {
  82     int ncases;
  83     char buf[Max_rule];
  84     char chr;
  85     scanf("%u\n", &ncases);
  86     forn (ci, ncases) {
  87         int nrules;
  88         scanf("%u\n", &nrules);
  89
  90         // rules[i][j] = cantidad de ocurrencias de Ai en la regla Aj -> ...
  91         Mat rules(N, Row(N, 0));
  92
  93         mat_identity(rules);
  94         forn (ri, nrules) {
  95             scanf("%c->%s\n", &chr, buf);
  96             assert(in_range(chr));
  97             forn (i, N) rules[i][charcode(chr)] = 0;
  98             const int rule_len = strlen(buf);
  99             forn (i, rule_len) {
 100                 assert(in_range(buf[i]));
 101                 rules[charcode(buf[i])][charcode(chr)]++;
 102             }
 103         }
 104
 105         int nqueries;
 106         int pow;
 107         scanf("%u\n", &nqueries);
 108         forn (qi, nqueries) {
 109             Mat input(N, Row(1, 0));
 110             scanf("%s %c %u\n", buf, &chr, &pow);
 111             // procesar regla
 112             const int input_len = strlen(buf);
 113             forn (i, input_len) {
 114                 assert(in_range(buf[i]));
 115                 input[charcode(buf[i])][0]++;
 116             }
 117
 118             Mat pow_rules(N, Row(N, 0));
 119             mat_pow(rules, pow, pow_rules);
 120
 121             Mat result(N, Row(1, 0));
 122             mat_mult(pow_rules, input, result);
 123
 124             cout << result[charcode(chr)][0] << endl;
 125         }
 126     }
 127     return 0;
 128 }